/**
 * 
 * dp[i][j] represents the maximum score with i nodes and j max-degrees.
 * 
 * Then, we add one node with k-degree, we could get:
 * dp[i+1][j+k] = Math.max(dp[i+1][j+k], score[k-1] + dp[i][j]);
 * 
 * At last, we only need to return the maximum value with 
 * N+1 (since N is the number of available degrees, which is nodes number - 1) nodes,
 * and 2*N degree.
 * */

/**
 * @author antonio081014
 * @since Dec 29, 2011, 9:54:00 AM
 */

public class P8XGraphBuilder {

	public int[][] dp;

	public int solve(int[] scores) {
		int N = scores.length;
		dp = new int[N + 2][2 * N + 2];
		for (int i = 0; i < N + 2; i++)
			for (int j = 0; j < 2 * N + 2; j++)
				dp[i][j] = Integer.MIN_VALUE;
		dp[0][0] = 0;
		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= 2 * N; j++) {
				if (dp[i][j] == Integer.MIN_VALUE)
					continue;
				for (int k = 1; k <= N && k + j <= 2 * N; k++) {
					dp[i + 1][j + k] = Math.max(dp[i + 1][j + k], scores[k - 1]
							+ dp[i][j]);
				}
			}
		}
		return dp[N + 1][2 * N];
	}
	// <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!
